package com.yohann.algorithm.dijkstra;

import java.util.Arrays;

/**
 * <p>
 * Dijkstra算法
 * </p>
 *
 * @author Yohann
 * @since 2021/1/25 21:02
 */
public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
        int[][] matrix = new int[vertex.length][vertex.length];
        final int n = 65535;
        matrix[0] = new int[]{n, 5, 7, n, n, n, 2};
        matrix[1] = new int[]{5, n, n, 9, n, n, 3};
        matrix[2] = new int[]{7, n, n, n, 8, n, n};
        matrix[3] = new int[]{n, 9, n, n, n, 4, n};
        matrix[4] = new int[]{n, n, 8, n, n, 5, 4};
        matrix[5] = new int[]{n, n, n, 4, 5, n, 6};
        matrix[6] = new int[]{2, 3, n, n, 4, 6, n};

        Graph graph = new Graph(vertex, matrix);
        graph.dsj(6);
        graph.showDijkstra();
    }
}

class Graph {
    private char[] vertex;
    private int[][] matrix;
    private VisitedVertex visitedVertex;

    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    public void show() {
        for (int[] link : matrix) {
            System.out.println(Arrays.toString(link));
        }
    }

    public void showDijkstra() {
        visitedVertex.show();
    }

    public void dsj(int index) {
        visitedVertex = new VisitedVertex(vertex.length, index);
        update(index);
        for (int i = 1; i < vertex.length; i++) {
            index = visitedVertex.updateArr();
            update(index);
        }
    }

    public void update(int index) {
        int len = 0;
        for (int i = 0; i < matrix[index].length; i++) {
            len = visitedVertex.getDis(index) + matrix[index][i];

            if (visitedVertex.in(i) && len < visitedVertex.getDis(i)) {
                visitedVertex.updatePre(i, index);
                visitedVertex.updateDis(i, len);
            }
        }
    }
}

class VisitedVertex {
    //已访问标记
    int[] alreadyArr;
    //前驱节点下标
    int[] preVisited;
    //出发顶点到其他顶点的距离
    int[] dis;

    public VisitedVertex(int length, int index) {
        this.alreadyArr = new int[length];
        this.preVisited = new int[length];
        this.dis = new int[length];
        Arrays.fill(dis, 65535);
        this.alreadyArr[index] = 1;
        this.dis[index] = 0;
    }

    //是否被访问过
    public boolean in(int index) {
        return alreadyArr[index] == 1;
    }

    //更新出发顶点到index的距离
    public void updateDis(int index, int length) {
        this.dis[index] = length;
    }

    //更新前驱节点
    public void updatePre(int pre, int index) {
        preVisited[pre] = index;
    }

    //获取出发顶点到index的距离
    public int getDis(int index) {
        return dis[index];
    }

    public int updateArr() {
        int min = 65535, index = 0;
        for (int i = 0; i < alreadyArr.length; i++) {
            if (alreadyArr[i] == 0 && dis[i] < min) {
                min = dis[i];
                index = i;
            }
        }

        alreadyArr[index] = 1;
        return index;
    }

    public void show() {
        System.out.println("===============================");
        System.out.println(Arrays.toString(alreadyArr));
        System.out.println(Arrays.toString(preVisited));
        System.out.println(Arrays.toString(dis));
        System.out.println("===============================");
    }
}